package SinglyLinkList

import "fmt"

type Object interface {

}

/*
 *单链表节点
 */
type SinglyNode struct {
	data Object
	nextData *SinglyNode
}

type SinglyLinkList struct{
	size uint
	head *SinglyNode
	tail *SinglyNode
}

//在链尾拼接节点
func (linkList *SinglyLinkList) Append(node *SinglyNode)bool{
	if node==nil {
		return false
	}
	if linkList.size==0 {	//链表长度为零，此插入节点为表头
		linkList.head = node
	}else{	//在链表的尾部追加元素，原表尾的下个节点为追加的元素
		oldTail := linkList.tail
		oldTail.nextData = node
	}
	linkList.tail = node
	linkList.size++
	return true
}

//插入节点
func (linkList *SinglyLinkList) Insert(node *SinglyNode,index uint)bool{
	if node==nil || index >linkList.size {
		return false
	}
	if index == 0 {	//如果插入的下标为表头，即替换表头，新的表头的下个元素为原表头
		node.nextData = linkList.head
		linkList.head = node
	}else{	//找到插入下标前一个位置的元素，该元素的下个节点为插入元素；插入元素的下个节点为原该位置的元素，
		tempNode := linkList.head
		for i:=uint(1);i<index;i++ {
			tempNode = tempNode.nextData
		}
		node.nextData = tempNode.nextData
		tempNode.nextData = node

		if linkList.size==index {	//如果插入下标为表尾，即该元素成为新的表尾
			linkList.tail = node
		}
	}
	linkList.size++
	return true
}

//删除下标节点
func (linkList *SinglyLinkList) Delete(index uint) bool{
	if index>=linkList.size {
		return false
	}


	if index == 0 {	//如果删除的为表头，新的表头为原表头的下个节点
		linkList.head=linkList.head.nextData
		if linkList.size == 2 {	//如果原链表长度为2，代表原链表只有表尾和表头，删除表头之后，表尾应设置为空
			linkList.tail = nil
		}
	}else{	//找到下标的元素和上一个元素，将上个元素的下个节点改为下标元素的下个节点，最后把下标元素的节点置为空
		preNode := linkList.head
		for i:=uint(1);i < index; i++ {
			preNode = preNode.nextData
		}
		node := preNode.nextData
		preNode.nextData = node.nextData
		node.nextData = nil
		if index==linkList.size-1 {
			linkList.tail = preNode
		}
	}

	linkList.size--
	return true
}

//获取下标节点
func (linkList *SinglyLinkList) Get(index uint) *SinglyNode{
	if index >= linkList.size {
		return nil
	}
	node := linkList.head

	for i:=uint(1);i<=index;i++{
		node = node.nextData
	}
	return node
}

//打印链表
func (linkList *SinglyLinkList) Println(){
	if linkList.size==0 {
		return
	}
	tempNode := linkList.head
	fmt.Println(tempNode.data)
	for i:=uint(1);i<linkList.size;i++  {
		tempNode = tempNode.nextData
		fmt.Println(tempNode.data)
	}
}
